// ================== Pacman 单文件教学版 ==================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <termios.h>
#include <fcntl.h>

// ================== 常量与类型定义区 ==================
#define MAP_ROWS 21
#define MAP_COLS 20
#define DOT '.'
#define WALL '#'
#define EMPTY ' '
#define PACMAN 'P'
#define GHOST 'G'
#define NAME_LEN 16
#define GHOST_COUNT 4

// --- 排行榜结构体 ---
/**
 * LeaderboardEntry: 排行榜条目结构体
 * - name: 玩家名
 * - score: 分数
 */
typedef struct {
    char name[NAME_LEN];
    int score;
} LeaderboardEntry;

// --- 二叉树结构体（通用） ---
/**
 * BinaryTreeNode: 通用二叉树节点
 * - name: 节点名称（本例用于技能树）
 * - left: 左子树指针
 * - right: 右子树指针
 */
typedef struct BinaryTreeNode {
    char name[16];
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BinaryTreeNode;

// ================== 数据结构层 ==================
// --- 队列（用于BFS） ---
/**
 * Point: 地图上的一个点（行、列坐标）
 */
typedef struct {
    int r, c;
} Point;
/**
 * Queue: 顺序队列，支持BFS操作
 * - data: 存储点的数组
 * - front, rear: 队头、队尾指针
 */
typedef struct {
    Point data[MAP_ROWS * MAP_COLS];
    int front, rear;
} Queue;
void queue_init(Queue* q) { q->front = q->rear = 0; }
int queue_empty(Queue* q) { return q->front == q->rear; }
void queue_push(Queue* q, int r, int c) {
    q->data[q->rear].r = r; q->data[q->rear].c = c; q->rear++;
}
Point queue_pop(Queue* q) { return q->data[q->front++]; }

// --- 排序（通用） ---
/**
 * sort: 通用排序函数（本例用于排行榜分数排序）
 * - arr: 排序对象数组
 * - n: 元素个数
 */
void sort(LeaderboardEntry* arr, int n) {
    // 冒泡排序，分数降序
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j].score < arr[j+1].score) {
                LeaderboardEntry tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

// --- 链表（通用，用于豆子） ---
/**
 * ListNode: 链表节点，存储一个豆子的位置
 * - row: 豆子在地图中的行坐标
 * - col: 豆子在地图中的列坐标
 * - next: 下一个节点指针
 */
typedef struct ListNode {
    int row, col; // 豆子在地图上的坐标
    struct ListNode* next;
} ListNode;
/**
 * LinkedList: 链表头结构体
 * - head: 链表头指针
 * - count: 链表节点数（豆子总数）
 */
typedef struct {
    ListNode* head;
    int count;
} LinkedList;

void LinkedList_init(LinkedList* list) {
    list->head = NULL;
    list->count = 0;
}
void LinkedList_insert(LinkedList* list, int row, int col) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->row = row; node->col = col; node->next = list->head;
    list->head = node;
    list->count++;
}
int LinkedList_remove(LinkedList* list, int row, int col) {
    ListNode* prev = NULL, *cur = list->head;
    while (cur) {
        if (cur->row == row && cur->col == col) {
            if (prev) prev->next = cur->next;
            else list->head = cur->next;
            free(cur); list->count--;
            return 1;
        }
        prev = cur; cur = cur->next;
    }
    return 0;
}
void LinkedList_free(LinkedList* list) {
    ListNode* cur = list->head;
    while (cur) {
        ListNode* tmp = cur; cur = cur->next; free(tmp);
    }
    list->head = NULL; list->count = 0;
}

// --- 二叉树相关函数（通用） ---
/**
 * BinaryTreeNode相关函数：创建、插入、遍历、统计等
 */
BinaryTreeNode* BinaryTree_create(const char* name) {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    strcpy(node->name, name);
    node->left = node->right = NULL;
    return node;
}
void BinaryTree_insert_left(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->left = child;
}
void BinaryTree_insert_right(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->right = child;
}
void BinaryTree_free(BinaryTreeNode* root) {
    if (!root) return;
    BinaryTree_free(root->left);
    BinaryTree_free(root->right);
    free(root);
}
// 提炼后的先序遍历方法，内部只做遍历
void BinaryTree_preorder(BinaryTreeNode* root) {
    if (!root) return;
    // 这里只做遍历，不处理节点
    BinaryTree_preorder(root->left);
    BinaryTree_preorder(root->right);
}
int BinaryTree_depth(BinaryTreeNode* root) {
    if (!root) return 0;
    int l = BinaryTree_depth(root->left);
    int r = BinaryTree_depth(root->right);
    return (l > r ? l : r) + 1;
}
int BinaryTree_count(BinaryTreeNode* root) {
    if (!root) return 0;
    return 1 + BinaryTree_count(root->left) + BinaryTree_count(root->right);
}
int BinaryTree_leaf_count(BinaryTreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return BinaryTree_leaf_count(root->left) + BinaryTree_leaf_count(root->right);
}
// --- 二叉树构造（技能树示例） ---
BinaryTreeNode* BinaryTree_sample() {
    BinaryTreeNode* root = BinaryTree_create("RootSkill");
    BinaryTreeNode* left = BinaryTree_create("Attack");
    BinaryTreeNode* right = BinaryTree_create("Defense");
    BinaryTreeNode* leftleft = BinaryTree_create("Accelerate");
    BinaryTreeNode* leftright = BinaryTree_create("More One Life");
    BinaryTreeNode* rightleft = BinaryTree_create("Cross Wall");
    BinaryTreeNode* rightright = BinaryTree_create("Unbeatable");
    BinaryTree_insert_left(root, left);
    BinaryTree_insert_right(root, right);
    BinaryTree_insert_left(left, leftleft);
    BinaryTree_insert_right(left, leftright);
    BinaryTree_insert_left(right, rightleft);
    BinaryTree_insert_right(right, rightright);
    return root;
}
// 外部函数：打印节点（原visit回调）
void print_node(BinaryTreeNode* node, int depth) {
    for (int i = 0; i < depth; i++) printf("  ");
    printf("%s\n", node->name);
}

// --- 图结构体与BFS ---
/**
 * Graph: 用于BFS的图结构体，直接用地图的墙和空地构建
 * - grid: 地图副本，墙体和空地信息
 */
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
} Graph;

void graph_init(Graph* g, char grid[MAP_ROWS][MAP_COLS]) {
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            g->grid[i][j] = grid[i][j];
}

// 通用BFS：返回完整路径
// path: 输出路径数组（调用者需分配足够空间），path[0]为起点，path[*path_len-1]为终点
// Point start: 起点坐标（行列）
// Point target: 终点坐标（行列）
// 返回路径长度，不可达返回0
int graph_bfs(Graph* g, Point start, Point target, Point* path, int* path_len) {
    if (start.r == target.r && start.c == target.c) {
        if (path) path[0] = start;
        if (path_len) *path_len = 1;
        return 1;
    }
    int vis[MAP_ROWS][MAP_COLS] = {0};
    Point pre[MAP_ROWS][MAP_COLS];
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            pre[i][j].r = pre[i][j].c = -1;
    Queue q; queue_init(&q);
    queue_push(&q, start.r, start.c); vis[start.r][start.c] = 1;
    int found = 0;
    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    while (!queue_empty(&q)) {
        Point p = queue_pop(&q);
        if (p.r == target.r && p.c == target.c) { found = 1; break; }
        for (int d = 0; d < 4; d++) {
            int nr = p.r + dr[d], nc = p.c + dc[d];
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS &&
                g->grid[nr][nc] != WALL && !vis[nr][nc]) {
                queue_push(&q, nr, nc); vis[nr][nc] = 1;
                pre[nr][nc] = p;
            }
        }
    }
    if (!found) { if (path_len) *path_len = 0; return 0; }
    // 回溯路径
    int len = 0;
    Point cur = target;
    Point tmp_path[MAP_ROWS * MAP_COLS];
    while (!(cur.r == start.r && cur.c == start.c)) {
        tmp_path[len++] = cur;
        cur = pre[cur.r][cur.c];
    }
    tmp_path[len++] = start;
    // 反转路径
    if (path) {
        for (int i = 0; i < len; i++) {
            path[i] = tmp_path[len-1-i];
        }
    }
    if (path_len) *path_len = len;
    return len;
}

// ================== 逻辑层 ==================
// --- 结构体定义 ---
/**
 * Map: 游戏地图结构体
 * - grid: 地图网格
 * - dots: 用链表管理的所有豆子
 */
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
    LinkedList dots; // 用链表管理豆子
} Map;
/**
 * Pacman: 玩家结构体
 * - row, col: 当前位置
 * - score: 当前分数
 * - lives: 剩余生命
 */
typedef struct {
    int row, col;
    int score;
    int lives;
} Pacman;
/**
 * Ghost: 幽灵结构体
 * - row, col: 当前位置
 */
typedef struct {
    int row, col;
} Ghost;

// --- 地图与豆子 ---
static char map_data[MAP_ROWS][MAP_COLS+1] = {
    "####################",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..................#",
    "#..##..####..##...#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#.................#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..##..####..##...#",
    "#..................#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "####################"
};
void map_init(Map* map) {
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map_data[i][j];
            map->grid[i][j] = c;
        }
    }
    LinkedList_init(&map->dots);
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            if (map->grid[i][j] == DOT) {
                LinkedList_insert(&map->dots, i, j);
            }
        }
    }
}
int map_eat_dot(Map* map, int row, int col) {
    if (map->grid[row][col] != DOT) return 0;
    int removed = LinkedList_remove(&map->dots, row, col);
    if (removed) {
        map->grid[row][col] = EMPTY;
        return 1;
    }
    return 0;
}

// --- Pacman与幽灵 ---
void pacman_init(Pacman* p, int row, int col) {
    p->row = row; p->col = col; p->score = 0; p->lives = 3;
}
void ghost_init(Ghost* g, int row, int col) {
    g->row = row; g->col = col;
}
void pacman_draw(Pacman* p, Map* map) {
    map->grid[p->row][p->col] = PACMAN;
}
void ghost_draw(Ghost* g, Map* map) {
    map->grid[g->row][g->col] = GHOST;
}

// --- 幽灵BFS追踪Pacman ---
void ghost_move(Map* map, Ghost* ghost, Pacman* pacman) {
    Graph g;
    graph_init(&g, map->grid);
    Point path[MAP_ROWS * MAP_COLS];
    int path_len;
    if (graph_bfs(&g, (Point){ghost->row, ghost->col}, (Point){pacman->row, pacman->col}, path, &path_len)) {
        if (path_len > 1) {
            ghost->row = path[1].r;
            ghost->col = path[1].c;
        }
        // 如果path_len==1，幽灵已在目标点，不动
    }
}

// --- 排行榜逻辑 ---
void leaderboardPrint(LeaderboardEntry* lb, int n) {
    printf("\n=== Leaderboard ===\n");
    for (int i = 0; i < n; i++) {
        printf("%-10s %d\n", lb[i].name, lb[i].score);
    }
}
// TODO: 可将排序等实现挖空

// ================== UI层 ==================
void map_draw(Map* map) {
    int ghost_color_idx = 0;
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map->grid[i][j];
            if (c == WALL) {
                int up = (i > 0 && map->grid[i-1][j] == WALL);
                int down = (i < MAP_ROWS-1 && map->grid[i+1][j] == WALL);
                int left = (j > 0 && map->grid[i][j-1] == WALL);
                int right = (j < MAP_COLS-1 && map->grid[i][j+1] == WALL);
                printf("\033[34m");
                if (up && down && left && right) printf("┼");
                else if (up && down && left) printf("┤");
                else if (up && down && right) printf("├");
                else if (left && right && up) printf("┴");
                else if (left && right && down) printf("┬");
                else if (down && right) printf("┌");
                else if (down && left) printf("┐");
                else if (up && right) printf("└");
                else if (up && left) printf("┘");
                else if (up || down) printf("│");
                else if (left || right) printf("─");
                else printf(" ");
                printf("\033[0m");
            } else if (c == DOT) {
                printf("\033[37m·\033[0m");
            } else if (c == PACMAN) {
                printf("\033[33mP\033[0m");
            } else if (c == GHOST) {
                const char* colors[4] = {"\033[31m", "\033[34m", "\033[33m", "\033[93m"};
                printf("%sG\033[0m", colors[ghost_color_idx]);
                ghost_color_idx = (ghost_color_idx + 1) % 4;
            } else {
                printf(" ");
            }
        }
        ghost_color_idx = 0;
        printf("\n");
    }
    printf("Dots left: %d\n", map->dots.count);
}
// TODO: 可将UI部分挖空

// --- 外部递归打印函数，遍历时传递深度并打印节点 ---
void binarytree_print_with_depth(BinaryTreeNode* root, int depth) {
    if (!root) return;
    for (int i = 0; i < depth; i++) printf("  ");
    printf("%s\n", root->name);
    binarytree_print_with_depth(root->left, depth+1);
    binarytree_print_with_depth(root->right, depth+1);
}

// --- 美化后的排行榜UI ---
void leaderboard_ui(LeaderboardEntry* lb, int n) {
    sort(lb, n);
    printf("\n\033[1;34m╔════════ Leaderboard ════════╗\033[0m\n");
    for (int i = 0; i < n; i++) {
        if (i == 0) // 第一名金色高亮
            printf("\033[1;33m│ %-10s \033[0m│ \033[1;32m%4d\033[0m │\n", lb[i].name, lb[i].score);
        else
            printf("\033[1;37m│ %-10s \033[0m│ \033[0;32m%4d\033[0m │\n", lb[i].name, lb[i].score);
    }
    printf("\033[1;34m╚═════════════════════════════╝\033[0m\n");
}

// --- 美化后的技能树打印 ---
void binarytree_print_with_color(BinaryTreeNode* node, int depth, int isLast, int isRoot) {
    for (int i = 0; i < depth; i++) printf("  ");
    if (depth > 0) {
        if (isLast)
            printf("\033[1;34m└─\033[0m");
        else
            printf("\033[1;34m├─\033[0m");
    }
    if (isRoot)
        printf("\033[1;36m%s\033[0m\n", node->name); // 根节点青色高亮
    else
        printf("\033[1;37m%s\033[0m\n", node->name); // 子节点白色
    // 递归打印左右子树
    if (node->left && node->right) {
        binarytree_print_with_color(node->left, depth+1, 0, 0);
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    } else if (node->left) {
        binarytree_print_with_color(node->left, depth+1, 1, 0);
    } else if (node->right) {
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    }
}

void binarytree_ui(BinaryTreeNode* root) {
    printf("\n\033[1;34m╔══════ Skill Tree ══════╗\033[0m\n");
    if (root)
        binarytree_print_with_color(root, 0, 1, 1);
    printf("\033[1;34m╚════════════════════════╝\033[0m\n");
    printf("\033[1;37mTotal Skills: \033[0m\033[1;32m%d\033[0m\n", BinaryTree_count(root));
    printf("\033[1;37mSkills Level(Tree Depth): \033[0m\033[1;32m%d\033[0m\n", BinaryTree_depth(root));
    printf("\033[1;37mReal Powerful Skills(Leaf count): \033[0m\033[1;32m%d\033[0m\n", BinaryTree_leaf_count(root));
}

// --- 终端输入辅助 ---
void set_terminal_raw() {
    struct termios term;
    tcgetattr(0, &term);
    term.c_lflag &= ~(ICANON | ECHO);
    tcsetattr(0, TCSANOW, &term);
}
void restore_terminal() {
    struct termios term;
    tcgetattr(0, &term);
    term.c_lflag |= ICANON | ECHO;
    tcsetattr(0, TCSANOW, &term);
}
int kbhit() {
    struct termios oldt, newt;
    int ch;
    int oldf;
    tcgetattr(STDIN_FILENO, &oldt);
    newt = oldt;
    newt.c_lflag &= ~(ICANON | ECHO);
    tcsetattr(STDIN_FILENO, TCSANOW, &newt);
    oldf = fcntl(STDIN_FILENO, F_GETFL, 0);
    fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK);
    ch = getchar();
    tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
    fcntl(STDIN_FILENO, F_SETFL, oldf);
    if (ch != EOF) {
        ungetc(ch, stdin);
        return 1;
    }
    return 0;
}
char getch() {
    char c;
    system("stty raw");
    c = getchar();
    system("stty cooked");
    return c;
}

// ================== 主函数 ==================
int main() {
    Map map;
    Pacman pacman;
    Ghost ghosts[GHOST_COUNT];
    LeaderboardEntry lb[5] = { {"Alice", 120}, {"Bob", 200}, {"Carol", 150}, {"You", 0}, {"Test", 0} };
    char playerName[NAME_LEN] = "You";
    srand(time(NULL));
    set_terminal_raw();
    map_init(&map);
    pacman_init(&pacman, 10, 10);
    ghost_init(&ghosts[0], 1, 2);
    ghost_init(&ghosts[1], 1, 17);
    ghost_init(&ghosts[2], 19, 2);
    ghost_init(&ghosts[3], 19, 17);
    int frame = 0;
    int running = 1;
    while (running) {
        system("clear");
        for (int i = 0; i < MAP_ROWS; i++)
            for (int j = 0; j < MAP_COLS; j++)
                if (map.grid[i][j] == PACMAN || map.grid[i][j] == GHOST)
                    map.grid[i][j] = EMPTY;
        pacman_draw(&pacman, &map);
        for (int i = 0; i < GHOST_COUNT; i++)
            ghost_draw(&ghosts[i], &map);
        map_draw(&map);
        printf("\nName: %s  Score: %d  Lives: %d\n", playerName, pacman.score, pacman.lives);
        if (kbhit()) {
            char key = getch();
            int dr = 0, dc = 0;
            if (key == 'w' || key == 'W') dr = -1;
            if (key == 's' || key == 'S') dr = 1;
            if (key == 'a' || key == 'A') dc = -1;
            if (key == 'd' || key == 'D') dc = 1;
            int nr = pacman.row + dr, nc = pacman.col + dc;
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS && map.grid[nr][nc] != WALL) {
                pacman.row = nr; pacman.col = nc;
                if (map_eat_dot(&map, nr, nc)) pacman.score += 10;
            }
        }
        // 让幽灵每隔两帧才移动一次
        if (frame % 2 == 0) {
            for (int i = 0; i < GHOST_COUNT; i++) {
                ghost_move(&map, &ghosts[i], &pacman);
                if (ghosts[i].row == pacman.row && ghosts[i].col == pacman.col) {
                    pacman.lives--;
                    if (pacman.lives <= 0) running = 0;
                }
            }
        }
        if (map.dots.count == 0) running = 0;
        usleep(120000);
        frame++;
    }
    restore_terminal();
    printf("\nGame Over!\n");
    lb[3].score = pacman.score;
    leaderboard_ui(lb, 5);
    BinaryTreeNode* skillroot = BinaryTree_sample();
    binarytree_ui(skillroot);
    BinaryTree_free(skillroot);
    LinkedList_free(&map.dots);
    return 0;
} 